// @algorithm @lc id=47 lang=cpp 
// @title permutations-ii


// @test([1])=[[1]]
// @test([1,1,2])=[[1,1,2],[1,2,1],[2,1,1]]
// @test([1,2,3])=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// @test([2,2,1,1])=[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
// @test([0,1,0,0,9])=[[0,0,0,1,9],[0,0,0,9,1],[0,0,1,0,9],[0,0,1,9,0],[0,0,9,0,1],[0,0,9,1,0],[0,1,0,0,9],[0,1,0,9,0],[0,1,9,0,0],[0,9,0,0,1],[0,9,0,1,0],[0,9,1,0,0],[1,0,0,0,9],[1,0,0,9,0],[1,0,9,0,0],[1,9,0,0,0],[9,0,0,0,1],[9,0,0,1,0],[9,0,1,0,0],[9,1,0,0,0]]
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        function<void(int)> dfs = [&](int cur){
            if(cur==nums.size()){
                ans.push_back(nums);
                return;
            }
            for(int i=cur; i<nums.size(); i++){
                // added from I: begin
                sort(nums.begin()+cur, nums.end());
                if(cur<i && nums[i-1]==nums[i]) continue;
                // added from I: end
                if(nums[cur]!=nums[i]) swap(nums[cur], nums[i]);
                dfs(cur+1);
                if(nums[cur]!=nums[i]) swap(nums[cur], nums[i]);
            }
        };
        dfs(0);
        return ans;
    }
};